package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.junit.Test;

/**
 * 4Sum
 * 
 * Given an array S of n integers, are there elements a, b, c, and d in S such
 * that a + b + c + d = target? Find all unique quadruplets in the array which
 * gives the sum of target.
 * 
 * Note: Elements in a quadruplet (a,b,c,d) must be in non-descending order.
 * (ie, a ≤ b ≤ c ≤ d) The solution set must not contain duplicate quadruplets.
 * For example, given array S = {1 0 -1 0 -2 2}, and target = 0.
 * 
 * A solution set is: (-1, 0, 0, 1) (-2, -1, 1, 2) (-2, 0, 0, 2)
 * 
 * @author yunzhang
 * 
 */
public class FourSum {
	/**
	 * Compute all possible two PairSums, store them in hashtable, them each
	 * time fetch one PairSums and check if another PairSum exists in the
	 * hashtable so their sum is target.
	 * 
	 * Best case complexity: 
	 *  O(n^2)
	 * Worst case complexity(consider an array of all 0's with target=0)
	 *  O(n^4)
	 *  
	 * @param num
	 * @param target
	 * @return
	 */
	public ArrayList<ArrayList<Integer>> fourSumHash(int[] num, int target) {
		ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();

		if (num == null || num.length < 4)
			return res;

		Arrays.sort(num);

		Set<Integer> checked = new HashSet<Integer>();
		Map<Integer, List<ArrayList<Integer>>> pairSums = new HashMap<Integer, List<ArrayList<Integer>>>();

		for (int i = 0; i < num.length - 1; ++i) {
			for (int j = i + 1; j < num.length; ++j) {
				int pairSum = num[i] + num[j];
				if (!pairSums.containsKey(pairSum)) {
					List<ArrayList<Integer>> newList = new ArrayList<ArrayList<Integer>>();
					pairSums.put(pairSum, newList);
				}
				ArrayList<Integer> pair = new ArrayList<Integer>();
				pair.add(i);
				pair.add(j);
				pairSums.get(pairSum).add(pair);
			}
		}

		for (Integer key : pairSums.keySet()) {
			if (!checked.contains(key)) {
				checked.add(key);

				if (pairSums.containsKey(target - key)) {
					checked.add(target - key);
					for (ArrayList<Integer> pair1 : pairSums.get(key)) {
						for (ArrayList<Integer> pair2 : pairSums.get(target
								- key)) {
							if (pair1.get(0) != pair2.get(0) && pair1.get(0) != pair2.get(1) &&
									pair1.get(1) != pair2.get(0) && pair1.get(1) != pair2.get(1)) {
								ArrayList<Integer> quadruplet = new ArrayList<Integer>();
								quadruplet.add(num[pair1.get(0)]);
								quadruplet.add(num[pair1.get(1)]);
								quadruplet.add(num[pair2.get(0)]);
								quadruplet.add(num[pair2.get(1)]);
								Collections.sort(quadruplet);
								if (!res.contains(quadruplet))
									res.add(quadruplet);
							}
						}
					}
				}
			}
		}

		return res;
	}

	/**
	 * O(n^3) algorithm similar as 3Sum and 3Sum closest
	 * 
	 * @param num
	 * @param target
	 * @return
	 */
	public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
		ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();

		if (num == null || num.length < 4)
			return res;

		Arrays.sort(num);

		for (int a = 0; a < num.length - 3; ++a) {
			if (a == 0 || num[a] != num[a - 1]) {
				for (int b = a + 1; b < num.length - 2; ++b) {
					if (b == a + 1 || num[b] != num[b - 1]) {
						int twoSum = target - num[a] - num[b];
						int c = b + 1;
						int d = num.length - 1;
						while (c < d) {
							int dist = twoSum - num[c] - num[d];
							if (dist == 0) {
								ArrayList<Integer> quadruplet = new ArrayList<Integer>();
								quadruplet.add(num[a]);
								quadruplet.add(num[b]);
								quadruplet.add(num[c]);
								quadruplet.add(num[d]);

								res.add(quadruplet);

								while (++c < d && num[c - 1] == num[c])
									;
								while (c < --d && num[d + 1] == num[d])
									;
							} else if (dist < 0) {
								while (c < --d && num[d + 1] == num[d])
									;
							} else {
								while (++c < d && num[c - 1] == num[c])
									;
							}
						}
					}
				}
			}
		}

		return res;
	}

	@Test
	public void test1() {
		FourSum fs = new FourSum();
		//int num[] = new int[] { 1,0,-1,0,-2,2 };
		int num[] = new int[] { 0,0,0,0 };
		int target = 0;

		fs.fourSumHash(num, target);
	}
}
